package offser;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * @version v1.0
 * @Description: 剑指offer-找出数组中重复的元素
 * @Author: TongRui乀
 * @Date: 2021/11/8 5:48 下午
 */
public class FindRepeatElement {

    public static void main(String[] args) {

        int[] arr = new int[]{1,5,3,6,8,1,3,7,0};
        // 题目1 找出数组中重复的数字。
        //在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，
        // 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
        function_1(arr);

        function_2(arr);
        // 题目2
        //在一个长度为 n+1 的数组里的所有数字都在 1 到 n 的范围内。 所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字。
        //但不能修改输入的数组。例如，如果输入长度为 7 的数组 {2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是第一个重复的数字 2 或 3 。
        Integer[] arr2 = new Integer[] {2, 3, 5, 4, 3, 2, 6, 7};
        function_3(arr2);

    }

    /**
     * @Description:  时间复杂度O(n) 空间复杂度 O(n)
     *              遍历元素并将元素放到哈希表中，每次先判断哈希表是否已经存在
     * @author TongRui乀
     * @date 2021/11/8 6:13 下午
     */
    private static void function_1(int[] arr){
        Map<Integer, Object> map = new HashMap<Integer, Object>();

        for (int i = 0; i < arr.length; i++) {
            var value = map.putIfAbsent(arr[i], arr[i]);
            if(Objects.nonNull(value)){
                System.out.println("重复元素："+arr[i]);
            }
        }
    }

    /**
     * @Description:
     *          思路： 将值为i的元素放到下表为i的位置
     *                遍历数组，当下表为i值为m时，判断m是否等于i，如果等于继续遍历
     *                如果不相等则将m与下表为m的元素进行比较 如果相等 说明出现重复元素，
     *                如果不相等 交换m与下表为m的元素
     *
     * 这个解法有个限制 就是数组中元素的大小不能大于数组的长度
     * @date 2021/11/8 6:22 下午
     */
    private static void function_2(int[] arr){

        for (int i = 0; i < arr.length; i++) {
            if(arr[i]<0 || arr[i] > arr.length){
                return;
            }
        }

        for (int i = 0; i < arr.length; i++) {

            if(i != arr[i]){
                if(arr[i] == arr[arr[i]]){
                    System.out.println("重复元素："+ arr[i]);
                }else {
                    int temp = arr[arr[i]];
                    arr[arr[i]] = arr[i];
                    arr[i] = temp;
                }
            }
        }
    }

    /**
     *  思路： 额外创建一个长度为n+1的数组, 遍历数组将每一个值m放到临时数组的以m为索引的位置
     *  如果m位置的值跟当前值相等就是重复了
     * @param arr
     */
    private static void function_3(Integer[] arr){

        int[] temp = new int[arr.length];

        for (int i = 0; i < arr.length; i++) {
            if(temp[arr[i]] == arr[i]){
                System.out.println("重复元素："+ arr[i]);
            }
            temp[arr[i]] = arr[i];
        }

    }
}
